// 给定一个二叉树和一个目标和，判断该树中是否存在根节点到叶子节点的路径，这条路径上所有节点值相加等于目标和。
// 思路1，递归
function hasPathSum(root, targetSum) {
    if (!root) {
        return false
    }
    if (!root.left && !root.right) {
        return targetSum - root.val === 0
    }
    return hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val)
}

// 思路2，遍历，前序遍历
function hasPathSum(root, targetSum) {
    if (!root) {
        return false
    }
    let stack = [root]
    let valStack = [0]
    while (stack.length) {
        let node = stack.pop()
        let curVal = valStack.pop()
        curVal += node.val
        if (!node.left && !node.right && curVal === targetSum) {
            return true
        }
        if (node.right) {
            stack.push(node.right)
            valStack.push(curVal)
        }
        if (node.left) {
            stack.push(node.left)
            valStack.push(curVal)
        }
    }
    return false
}